public class MaxGrade {
    public static void main(String[] args) {
        MaxGrade_fun2();
        MaxGrade_fun1();
    }
    /**
     * 贪心算法
     */
    public static void MaxGrade_fun2(){
        int[] Grade = {7,8,6,2,5,8,9,6};
        int n = Grade.length;
        int sum=0,max = 0,l = 0,r = 0,len = 0; //max是递增的，无需赋值
        for (int i = 1; i < n; i++) {
            // 计算
            for (int j = 0; j < n-i; j++) {
                len = j+1;
                while (Grade[len] == 0){
                    len++;
                }
                if(Grade[j] + Grade[len] > max){
                    max = Grade[j] + Grade[len];
                    l = j;
                    r = len;
                }
            }
            // 结果输出
            for (int j = 0; j < n; j++) {
                if(Grade[j] == 0)
                    continue;
                if(j == l){
                    System.out.print("[" + Grade[j]+"\t");
                    continue;
                }
                else  if(j == r){
                    System.out.print(Grade[j]+"]"+"\t");
                    continue;
                }
                else
                    System.out.print(Grade[j]+"\t");
            }
            Grade[l]  += Grade[r];
            Grade[r] = 0;
            sum+=max;
            System.out.println("\nGrade = "+Grade[l]);
        }
        System.out.println("贪心算法： "+sum);
    }

    /**
     * 区间动态规划
     */
    public static void MaxGrade_fun1(){
        int[] Grade = {7,8,6,2,5,8,9,6};
        int[]   sum = new int[30000];
        int dp[][]  = new int[30000][30000];
        int n = Grade.length;
        for(int i = 1; i <= n; i++){
            sum[i]   = sum[i-1] + Grade[i-1];
        }
        for(int i = n; i >= 1; i--){
            for(int j = i+1; j <= n; j++){
                int tmp = 0;
                for(int k = i; k < j; k++)
                    tmp = Math.max(tmp,dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
                dp[i][j] = tmp;
            }
        }
        for (int i = 1; i <=n; i++) {
            for (int j = 1; j <=n ; j++) {
                System.out.print(dp[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println("区间动态规划： "+dp[1][n]);


    }
}
